package algorighm.class007;

import java.io.File;
import java.util.ArrayList;

public class Code01_RecursiveExample {
    // 斐波那契数列（Fibonacci）

    public static int fibonacci(int n) {
        if (n <= 1) { // 基准条件
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用
        }
    }

    public static void main1(String[] args) {
        System.out.println(fibonacci(6)); // 输出 8 (0,1,1,2,3,5,8)
    }
	// --------------------------------------------
	// 汉诺塔问题（Tower of Hanoi）
	public static void hanoi(int n, char from, char to, char aux) {
		if (n == 1) {  // 基准条件：只有一个盘子时直接移动
			System.out.println("Move disk 1 from " + from + " to " + to);
		} else {
			hanoi(n - 1, from, aux, to);  // 把 n-1 个盘子从 from 移到 aux
			System.out.println("Move disk " + n + " from " + from + " to " + to);
			hanoi(n - 1, aux, to, from);  // 把 n-1 个盘子从 aux 移到 to
		}
	}

	public static void main2(String[] args) {
		hanoi(3, 'A', 'C', 'B');  // 3个盘子，从A移到C，借助B
	}
	// --------------------------------------------
	// 二分查找（Binary Search）
	public static int binarySearch(int[] arr, int target, int low, int high) {
		if (low > high) {  // 基准条件：未找到
			return -1;
		}
		int mid = low + (high - low) / 2;
		if (arr[mid] == target) {
			return mid;  // 找到目标
		} else if (arr[mid] < target) {
			return binarySearch(arr, target, mid + 1, high);  // 在右半部分查找
		} else {
			return binarySearch(arr, target, low, mid - 1);  // 在左半部分查找
		}
	}

	public static void main3(String[] args) {
		int[] arr = {1, 3, 5, 7, 9};
		int target = 5;
		int index = binarySearch(arr, target, 0, arr.length - 1);
		System.out.println("Found at index: " + index);  // 输出 2
	}
	// --------------------------------------------
	// 递归遍历文件夹（目录递归）
	public static void listFiles(File dir) {
		if (dir.isDirectory()) {
			File[] files = dir.listFiles();
			if (files != null) {
				for (File file : files) {
					if (file.isDirectory()) {
						listFiles(file);  // 递归进入子目录
					} else {
						System.out.println(file.getAbsolutePath());
					}
				}
			}
		}
	}

	public static void main4(String[] args) {
		File directory = new File("C:/example");
		listFiles(directory);
	}
	// --------------------------------------------

	// --------------------------------------------
}
